/**
 * @param {number[]} values
 * @return {number}
 */
var minScoreTriangulation = function (values) {
  const n = values.length;
  // dp[i][j] 表示顶点 i 到 j 构成的多边形的最低得分
  const dp = new Array(n).fill(0).map(() => new Array(n).fill(0));

  // 按多边形的长度 len 从小到大进行计算
  // len=2 时，只有两个顶点，无法构成三角形，得分是 0 (已在初始化中完成)
  // 所以我们从 len=3 开始计算
  for (let len = 3; len <= n; len++) {
    // 遍历所有长度为 len 的多边形的起点 i
    for (let i = 0; i <= n - len; i++) {
      const j = i + len - 1; // 计算终点 j
      dp[i][j] = Infinity; // 初始化一个较大的值，用于后续取最小值

      // 遍历所有可能的分割点 k
      for (let k = i + 1; k < j; k++) {
        // 状态转移方程
        const currentScore =
          dp[i][k] + dp[k][j] + values[i] * values[k] * values[j];
        dp[i][j] = Math.min(dp[i][j], currentScore);
      }
    }
  }

  // 最终结果是整个多边形的最低得分
  return dp[0][n - 1];
};

// --- 示例 ---
console.log(minScoreTriangulation([1, 2, 3])); // 输出: 6
console.log(minScoreTriangulation([3, 7, 4, 5])); // 输出: 144
console.log(minScoreTriangulation([1, 3, 1, 4, 1, 5])); // 输出: 13
